RSA Factoring Challenge

The RSA Factoring Challenge was a challenge put forward by RSA Laboratories on March 18, 1991 to encourage research into computational number theory and the practical difficulty of factoring large integers and cracking RSA keys used in cryptography. They published a list of semiprimes (numbers with exactly two prime factors) known as the RSA numbers, with a cash prize for the successful factorization of some of them. The smallest of them, a 100 decimal digit number called RSA-100 was factored by April 1, 1991, but many of the bigger numbers have still not been factored and are expected to remain unfactored for quite some time.

The RSA challenges ended in 2007.[1] RSA Laboratories stated: "Now that the industry has a considerably more advanced understanding of the cryptanalytic strength of common symmetric-key and public-key algorithms, these challenges are no longer active."[2]

The factoring challenge was intended to track the cutting edge in integer factorization. A primary application is for choosing the key length of the RSA public-key encryption scheme. Progress in this challenge should give an insight into which key sizes are still safe and for how long. As RSA Laboratories is a provider of RSA-based products, the challenge was used by them as an incentive for the academic community to attack the core of their solutions — in order to prove its strength.

The RSA numbers were generated on a computer with no network connection of any kind. The computer's hard drive was subsequently destroyed so that no record would exist, anywhere, of the solution to the factoring challenge.[3]

The first RSA numbers generated, RSA-100 to RSA-500 and RSA-617, were labeled according to their number of decimal digits; the other RSA numbers (beginning with RSA-576) were generated later and labelled according to their number of binary digits.

Contents

The mathematics

RSA Laboratories states that: for each RSA number n, there exist prime numbers p and q such that

n = p × q.

The problem is to find these two primes, given only n.

The prizes and records

The following table gives an overview over all RSA numbers.

The challenge numbers in pink lines are numbers expressed in base 10, while the challenge numbers in yellow lines are numbers expressed in base 2. The prizes for RSA-576 and RSA-640 have been awarded. The remaining prizes have been retracted since the challenge became inactive in 2007.
RSA Number Decimal digits Binary digits Cash prize offered Factored on Factored by
RSA-100 100 330 $1,000 USD April 1, 1991 Arjen K. Lenstra
RSA-110 110 364 $4,429 USD April 14, 1992 Arjen K. Lenstra and M.S. Manasse
RSA-120 120 397 $5,898 July 9, 1993 T. Denny et al.
RSA-129 129 426 $100 USD[4] April 26, 1994 Arjen K. Lenstra et al.
RSA-130 130 430 $14,527 USD April 10, 1996 Arjen K. Lenstra et al.
RSA-140 140 463 $17,226 USD February 2, 1999 Herman te Riele et al.
RSA-150[5] 150 496   April 16, 2004 Kazumaro Aoki et al.
RSA-155 155 512 $9,383 August 22, 1999 Herman te Riele et al.
RSA-160 160 530   April 1, 2003 Jens Franke et al., University of Bonn
RSA-170 170 563   December 29, 2009 D. Bonenberger and M. Krone
RSA-576 174 576 $10,000 USD December 3, 2003 Jens Franke et al., University of Bonn
RSA-180 180 596   May 8, 2010 S. A. Danilov and I. A. Popovyan, Moscow State University
RSA-190 190 629   November 8, 2010 A. Timofeev and I. A. Popovyan
RSA-640 193 640 $20,000 USD November 2, 2005 Jens Franke et al., University of Bonn
RSA-200 200 663   May 9, 2005 Jens Franke et al., University of Bonn
RSA-210 210 696   inactive
RSA-704 212 704 $30,000 USD inactive, prize retracted
RSA-220 220 729   inactive
RSA-230 230 762   inactive
RSA-232 232 768   inactive
RSA-768 232 768 $50,000 USD December 12, 2009 Thorsten Kleinjung et al. (prize retracted)
RSA-240 240 795   inactive
RSA-250 250 829   inactive
RSA-260 260 862   inactive
RSA-270 270 895   inactive
RSA-896 270 896 $75,000 USD inactive, prize retracted
RSA-280 280 928   inactive
RSA-290 290 962   inactive
RSA-300 300 995   inactive
RSA-309 309 1024   inactive
RSA-1024 309 1024 $100,000 USD inactive, prize retracted
RSA-310 310 1028   inactive
RSA-320 320 1061   inactive
RSA-330 330 1094   inactive
RSA-340 340 1128   inactive
RSA-350 350 1161   inactive
RSA-360 360 1194   inactive
RSA-370 370 1227   inactive
RSA-380 380 1261   inactive
RSA-390 390 1294   inactive
RSA-400 400 1327   inactive
RSA-410 410 1360   inactive
RSA-420 420 1393   inactive
RSA-430 430 1427   inactive
RSA-440 440 1460   inactive
RSA-450 450 1493   inactive
RSA-460 460 1526   inactive
RSA-1536 463 1536 $150,000 USD inactive, prize retracted
RSA-470 470 1559   inactive
RSA-480 480 1593   inactive
RSA-490 490 1626   inactive
RSA-500 500 1659   inactive
RSA-617 617 2048   inactive
RSA-2048 617 2048 $200,000 USD inactive, prize retracted

See also

Notes

  1. ^ RSA Laboratories, The RSA Factoring Challenge. Retrieved on 2007-05-18.
  2. ^ RSA Laboratories, The RSA Factoring Challenge FAQ. Retrieved on 2007-05-30.
  3. ^ RSA Laboratories. "The RSA Factoring Challenge FAQ". http://www.rsa.com/rsalabs/node.asp?id=2094#HowWereTheNumbersGenerated. Retrieved 2008-08-05. 
  4. ^ RSA-129 was not part of the RSA Factoring Challenge, but was related to a column by Martin Gardner in Scientific American.
  5. ^ RSA-150 was withdrawn from the original challenge by RSA Security, but was factored anyway.

External links